package tree;

import java.util.Stack;

/**
 * 98. 验证二叉搜索树
 *
 * @author Api
 * @date 2023/10/25 23:12
 */
public class Code98_VerifyBinarySearchTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //使用統一迭代法(效率较低)
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        if (root != null) {
            stack.add(root);
        }
        while (!stack.isEmpty()) {
            TreeNode curr = stack.peek();
            if (curr != null) {
                stack.pop();
                if (curr.right != null) {
                    stack.add(curr.right);
                }
                stack.add(curr);
                stack.add(null);
                if (curr.left != null) {
                    stack.add(curr.left);
                }
            } else {
                stack.pop();
                TreeNode temp = stack.pop();
                if (pre != null && pre.val >= temp.val) {
                    return false;
                }
                pre = temp;
            }
        }
        return true;
    }

    // 递归 (中序遍历)
    TreeNode max;

    public boolean isValidBST1(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST1(root.left);
        if (!left) {
            return false;
        }
        // 中
        if (max != null && root.val <= max.val) {
            return false;
        }
        max = root;
        // 右
        boolean right = isValidBST1(root.right);
        return right;
    }

    public boolean isValidBST2(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left; // 左
            }
            // 中，处理
            TreeNode pop = stack.pop();
            if (pre != null && pop.val <= pre.val) {
                return false;
            }
            pre = pop;
            root = pop.right; // 右
        }
        return true;
    }
}
